As a target application for the present invention, the Internet provides a connectionless, end-to-end packet service using an established IP protocol. Communication on the Internet depends on congestion avoidance mechanisms implemented in the transport layer protocols, like TCP, to provide good service under heavy load. However, either deliberately or by accident, many TCP implementations do not include a congestion-avoidance mechanism. Moreover, there are a growing number of UDP-based applications running in the Internet, such as packet voice and packet video, involving data flows that do not back off properly when they receive congestion indications. As a result, these applications aggressively use up more bandwidth than other TCP compatible flows. This could eventually cause “Internet Meltdown,” for example as discussed in Recommendations on Queue Management and Congestion Avoidance in the Internet, by B. Braden et al., IETF RFC (Informational) 2309, April 1998, and Data Networks, by D. Bertsekas and R. Gallager, Second edition, Prentice Hall, 1992. To mitigate the severity of this problem, router mechanisms have been developed to shield responsive flows from unresponsive or aggressive flows and to provide a good quality of service (QoS) to all users.
Two types of router algorithms for achieving congestion control are broadly classified under the monikers “scheduling algorithms” and “queue management algorithms.” A generic scheduling algorithm, exemplified by the well-known Fair Queuing (FQ) algorithm, looks for the buffer at each output of a router to be partitioned into separate queues each of which will buffer the packets of one of the flows. Packets from the flow buffers are placed on the outgoing line by a scheduler using an approximate bit-by-bit, round-robin discipline. Because the queuing of the packets is based on the respective packet flows, packets belonging to different flows are essentially isolated from each other and, advantageously, one flow cannot degrade the quality of another. Achieving this flow isolation, however, requires unduly complicated per-flow state information, thereby rendering implementations impracticable for many applications.
Specific scheduling algorithms have attempted to reduce both the operating complexities and the cost of maintaining flow state information. For example, in one method, routers are divided into two categories: edge routers and core routers. An edge router keeps per-flow state information and estimates each flow's arrival rate. These estimates are inserted into the packet headers and passed on to the core routers. A core router maintains a stateless FIFO queue and, during periods of congestion, drops a packet randomly based on the rate estimates. This scheme reduces the core router's design complexity, but the edge router's design is still overly complex. Also, because of the rate information in the header, the core routers have to extract packet information differently than traditional routers extract packet information; this additional packet-extraction step adds even further complexity. In an effort to approximate the FQ algorithm with less implementation complexity, another scheme uses a hash function to classify packets into a smaller number of queues than the number of queues used by the FQ algorithm. This approach, however, still requires around 1000 to 2000 queues in a typical router to approach the performance of the FQ algorithm.
The queue management class of router algorithms attempts to approximate fairness using a simpler design. An example of this class of algorithms is Random Early Detection (“RED”). A router algorithm implementing RED maintains a single FIFO to be shared by all the packet flows, and drops an arriving packet at random during periods of congestion. The probability of dropping a packet increases with the level of congestion. Since RED acts in anticipation of congestion, it does not suffer from “lock out” and “full Queue” problems described in “Recommendations on Queue Management and Congestion Avoidance in the Internet.” By keeping the average queue-size small, RED reduces the degree of delays experienced by most typical flows. However, because the percentage of packets dropped from each flow over a period of time is almost the same, the ability of RED to penalize unresponsive flows is limited. Consequently, misbehaving traffic can take up a large percentage of the link bandwidth and starve out TCP-friendly flows.
Variations to the RED approach have attempted to improve the ability for distinguishing unresponsive users. However, these variants have typically incurred extra implementation overhead. One such variant stores information about unfriendly flows, and another requires information about active connections. Yet another approach stabilizes the occupancy of the FIFO buffer, independently of the number of active flows.
Accordingly, the scheduling-type router algorithms provide a fair bandwidth allocation but are often too complex for high-speed implementations and do not scale well to a large number of users. The queue-management router algorithms are relatively simple to implement but fail to penalize misbehaving flows and therefore do not provide bandwidth allocation with a comparable degree of fairness. Hybrid algorithms have provided compromises on fairness or have added undue complexity. In view of the classes of router algorithms manifesting the inability to provide both fairness and simple implementation simultaneously, as discussed in “Efficient Active Queue Management for Internet Routers,” by B. Suter et al., Interop 98, it has been concluded that the two goals present opposing tensions and are unlikely to be realized at the same time.